Edmonds' algorithm

In graph theory, a branch of mathematics, Edmonds' algorithm or Chu–Liu/Edmonds' algorithm is an algorithm for finding a maximum or minimum optimum branchings. When nodes are connected by weighted edges that are directed, a minimum spanning tree algorithm cannot be used. Instead an optimum branching algorithm should be applied using the algorithm proposed independently first by Yoeng-jin Chu and Tseng-hong Liu (1965) and then by Edmonds (1967). To find a maximum path length, the largest edge value is found and connected between the two nodes, then the next largest value, and so on. If an edge creates a loop, it is erased. A minimum path length is found by starting from the smallest value.

1 Order
2 Algorithm
- 2.1 Description
- 2.2 Implementation
3 References
4 External links

Order

The order of this algorithm is $O(EV)$ . There is a faster implementation of the algorithm by Robert Tarjan. The order is $O(E \log V)$ for a sparse graph and $O(V^2)$ for a dense graph. This is as fast as Prim's algorithm for an undirected minimum spanning tree. In 1986, Gabow, Galil, Spencer, and Tarjan made a faster implementation, and its order is $O(E %2B V \log V)$ .

Algorithm

Description

The algorithm has a conceptual recursive description. We will denote by $f$ the function which, given a weighted directed graph $D$ with a distinguished vertex $r$ called the root, returns a spanning tree rooted at $r$ of minimal cost.

The precise description is as follows. Given a weighted directed graph $D$ with root $r$ we first replace any set of parallel edges (edges between the same pair of vertices in the same direction) by a single edge with weight equal to the minimum of the weights of these parallel edges.

Now, for each node $v$ other than the root, mark an (arbitrarily chosen) incoming edge of lowest cost. Denote the other endpoint of this edge by $\pi(v)$ . If the marked edges form an SRT, $f(D)$ is defined to be this SRT. Otherwise, the set of marked edges form at least one cycle. Call (an arbitrarily chosen) one of these cycles $C$ . We now define a weighted directed graph $D^\prime$ having a root $r^\prime$ as follows. The nodes of $D^\prime$ are the nodes of $D$ not in $C$ plus a new node denoted $v_C$ . If $(u,v)$ is an edge in $D$ with $u\notin C$ , include the edge $e$ described below, in $D^\prime$ .

If $v\in C$ , $e = (u, v_C)$ , and $w(e) = w(u,v) - w(\pi(v),v)$ . Otherwise, if $v\notin C$ , let $e = (u,v)$ , and $w(e) = w(u,v)$ .

We include no other edges in $D^\prime$ .

The root $r^\prime$ of $D^\prime$ is simply the root $r$ in $D$ .

Using a call to $f(D^\prime)$ , find an SRT in $D^\prime$ . Suppose in this SRT, the (unique) incoming edge at $v_C$ is $(u, v_C)$ . This edge comes from some pair $(u,v)$ with $u\notin C$ and $v\in C$ . Unmark $(\pi(v),v)$ and mark $(u,v)$ . Now the set of marked edges do form an SRT, which we define to be the value of $f(D)$ .

Observe that $f(D)$ is defined in terms of $f(D^\prime)$ for weigthed directed rooted graphs $D^\prime$ having strictly fewer vertices than $D$ , and finding $f(D)$ for a single-vertex graph is trivial.

Implementation

Let BV be a vertex bucket and BE be an edge bucket. Let v be a vertex and e be an edge of maximum positive weight that is incident to v. C_i is a circuit. G₀ = (V₀,E₀) is the original digraph. u_i is a replacement vertex for C_i.


i=0

A:
if  then goto B
for some vertex  and  {
   
   find an edge  such that w(e) = max{ w(y,v)|(y,v)  E_i}
   if w(e) ≤ 0 then goto A
}
if  contains a circuit {
   i=i+1
   construct  by shrinking  to 
   modify BE, BV and some edge weights
}

goto A

B:
while i ≠ 0 {
   reconstruct  and rename some edges in BE
   if  was a root of an out-tree in BE {
        and 
   }else{
        and 
   }
   i=i-1
}
Maximum branching weight =

References

Y. J. Chu and T. H. Liu, "On the Shortest Arborescence of a Directed Graph", Science Sinica, vol. 14, 1965, pp. 1396–1400.
J. Edmonds, “Optimum Branchings”, J. Res. Nat. Bur. Standards, vol. 71B, 1967, pp. 233–240.
R. E. Tarjan, "Finding Optimum Branchings", Networks, v.7, 1977, pp. 25–35.
P.M. Camerini, L. Fratta, and F. Maffioli, "A note on finding optimum branchings", Networks, v.9, 1979, pp. 309–312.
Alan Gibbons Algorithmic Graph Theory, Cambridge University press, 1985 ISBN 0-521-28881-9
H. N. Gabow, Z. Galil, T. Spencer, and R. E. Tarjan, “Efficient algorithms for finding minimum spanning trees in undirected and directed graphs,” Combinatorica 6 (1986), 109-122.

External links

The Directed Minimum Spanning Tree Problem Description of the algorithm summarized by Shanchieh Jay Yang, May 2000.
Edmonds's algorithm ( edmonds-alg ) – An open source implementation of Edmonds's algorithm written in C++ and licensed under the MIT License. This source is using Tarjan's implementation for the dense graph.
AlgoWiki – Edmonds's algorithm - A public-domain implementation of Edmonds's algorithm written in Java.